Deterministic Finite Automaton

Definition 定义

确定性有限自动机（DFA）：一种用于识别（接受）正则语言的抽象计算模型。它由有限个状态、输入字母表、状态转移函数、起始状态和接受状态集合组成；“确定性”指对任意状态与输入符号，下一状态唯一确定。

Pronunciation 发音

/ˌdɪtɝːməˈnɪstɪk ˈfaɪnaɪt ˌɔːtəˈmætən/

Examples 例句

A deterministic finite automaton can check whether a string matches a simple pattern.
确定性有限自动机可以检查一个字符串是否匹配简单模式。

In compiler design, a deterministic finite automaton is often used to implement the lexer by recognizing tokens from regular expressions.
在编译器设计中，确定性有限自动机常用于实现词法分析器，通过识别由正则表达式描述的记号（token）。

Etymology 词源

deterministic 源自 determine（决定、确定），强调“结果唯一、无歧义”；finite 表示“有限的（状态数有限）”；automaton 来自希腊语 automatos（“自行动的”），在计算理论中指能按规则自动进行状态转移的抽象机器。该术语在20世纪形式语言与自动机理论发展中定型，用来与 nondeterministic finite automaton (NFA) 区分。

Related Words 相关词汇

• Automaton
• Finite-State Machine
• Nondeterministic
• NFA
• Regular Expression
• Regular Language
• State
• Transition Function
• Minimization
• Lexer

Notable Works 文献与作品

• Introduction to Automata Theory, Languages, and Computation（Hopcroft, Motwani, Ullman）：系统介绍 DFA/NFA 与正则语言的等价性等核心内容。
• Introduction to the Theory of Computation（Michael Sipser）：以 DFA 为基础讲解可计算性与复杂性前置的形式化工具。
• Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman，“龙书”）：在词法分析章节中用 DFA/自动机构造来实现 token 识别。